package pers.qianyu.month_202012.date_20201203;

/**
 * [Leetcode 每日一题]
 * 204. 计数质数
 * https://leetcode-cn.com/problems/count-primes/
 *
 * @author mizzle rain
 * @date 2020-12-03 14:43
 */
public class CountPrimes2 {
    /**
     * 埃氏筛
     */
    public int countPrimes(int n) {
        int[] arr = new int[n];
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (arr[i] == 0) {
                res++;
                // 注意这里要先转成 long 再相乘，不能先相乘再转成 long
                if (((long) i) * i < n) {
                    for (int k = i * i; k < n; k += i) {
                        arr[k] = 1;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int result = new CountPrimes2().countPrimes(10);
        System.out.println("result = " + result);
    }
}
